﻿#include <iostream>

static bool isExpressVaild(const char* express)
{
	auto n = strlen(express);
	if (n % 2 == 0) return false;

	for (int i = 0; i < n; i += 2)
	{
		char c = express[i];
		if (c != '1' && c != '0')
			return false;
	}

	for (int i = 1; i < n; i += 2)
	{
		char c = express[i];
		if (c != '&' && c != '|' && c != '^')
			return false;
	}

	return true;
}

static int recur(const char* express, bool desired, int left, int right)
{
	if (left == right)
	{
		if (desired) return express[left] == '1' ? 1 : 0;
		else return express[left] == '0' ? 1 : 0;
	}

	int combinationCount = 0;
	for (int i = left + 1; i < right; i += 2)
	{
		char c = express[i];
		int l = i - 1;
		int r = i + 1;
		switch (c)
		{
		case '&':
			if (desired)
			{
				int a = recur(express, true, left, l);
				int b = recur(express, true, r, right);
				combinationCount += a * b;
			}
			else
			{
				int a = recur(express, true, left, l);
				int b = recur(express, false, r, right);
				int c = recur(express, false, left, l);
				int d = recur(express, true, r, right);
				combinationCount += a * b + c * d + b * c;
			}
			break;

		case '|':
			if (desired)
			{
				int a = recur(express, true, left, l);
				int b = recur(express, false, r, right);
				int c = recur(express, false, left, l);
				int d = recur(express, true, r, right);
				combinationCount += a * b + c * d + a * d;
			}
			else
			{
				int a = recur(express, false, left, l);
				int b = recur(express, false, r, right);
				combinationCount += a * b;
			}
			break;

		case '^':
			if (desired)
			{
				int a = recur(express, true, left, l);
				int b = recur(express, false, r, right);
				int c = recur(express, false, left, l);
				int d = recur(express, true, r, right);
				combinationCount += a * b + c * d;
			}
			else
			{
				int a = recur(express, true, left, l);
				int b = recur(express, true, r, right);
				int c = recur(express, false, left, l);
				int d = recur(express, false, r, right);
				combinationCount += a * b + c * d;
			}
			break;
		}
	}

	return combinationCount;
}

static int byStrictTable(const char* express, bool desired)
{
	int lSize = strlen(express);
	int rSize = strlen(express);
	int* dp = (int*)malloc(lSize * rSize * 2 * sizeof(int));
	memset(dp, 0, lSize * rSize * 2 * sizeof(int));

	// dp[b, right, left] = dp[left + right * lSize + b * lSize * rSize]
	for (int left = 0; left < lSize; left++)
	{
		dp[left + left * lSize] = express[left] == '0' ? 1 : 0;
		dp[left + left * lSize + lSize * rSize] = express[left] == '1' ? 1 : 0;
	}

	for (int offset = 2; offset < rSize; offset += 2)
	{
		for (int left = 0; left < lSize; left += 2)
		{
			int right = left + offset;
			if (right >= rSize) continue;

			int combinationCount1 = 0;
			int combinationCount0 = 0;
			for (int i = left + 1; i < right; i += 2)
			{
				char c = express[i];
				int l = i - 1;
				int r = i + 1;
				switch (c)
				{
				case '&':
					//if (desired)
					{
						int a = dp[left + l * lSize + lSize * rSize];//recur(express, true, left, l);
						int b = dp[r + right * lSize + lSize * rSize];//recur(express, true, r, right);
						combinationCount1 += a * b;
					}
					//else
					{
						int a = dp[left + l * lSize + lSize * rSize];//recur(express, true, left, l);
						int b = dp[r + right * lSize];//recur(express, false, r, right);
						int c = dp[left + l * lSize];//recur(express, false, left, l);
						int d = dp[r + right * lSize + lSize * rSize];//recur(express, true, r, right);
						combinationCount0 += a * b + c * d + b * c;
					}
					break;

				case '|':
					//if (desired)
					{
						int a = dp[left + l * lSize + lSize * rSize];//recur(express, true, left, l);
						int b = dp[r + right * lSize];//recur(express, false, r, right);
						int c = dp[left + l * lSize];//recur(express, false, left, l);
						int d = dp[r + right * lSize + lSize * rSize];//recur(express, true, r, right);
						combinationCount1 += a * b + c * d + a * d;
					}
					//else
					{
						int a = dp[left + l * lSize];//recur(express, false, left, l);
						int b = dp[r + right * lSize];//recur(express, false, r, right);
						combinationCount0 += a * b;
					}
					break;

				case '^':
					//if (desired)
					{
						int a = dp[left + l * lSize + lSize * rSize];//recur(express, true, left, l);
						int b = dp[r + right * lSize];//recur(express, false, r, right);
						int c = dp[left + l * lSize];//recur(express, false, left, l);
						int d = dp[r + right * lSize + lSize * rSize];//recur(express, true, r, right);
						combinationCount1 += a * b + c * d;
					}
					//else
					{
						int a = dp[left + l * lSize + lSize * rSize];//recur(express, true, left, l);
						int b = dp[r + right * lSize + lSize * rSize];//recur(express, true, r, right);
						int c = dp[left + l * lSize];//recur(express, false, left, l);
						int d = dp[r + right * lSize];//recur(express, false, r, right);
						combinationCount0 += a * b + c * d;
					}
					break;
				}
			}

			dp[left + right * lSize] = combinationCount0;
			dp[left + right * lSize + lSize * rSize] = combinationCount1;
		}
	}
	
	int res = desired ? dp[(lSize - 1) * lSize + lSize * rSize] : dp[(lSize - 1) * lSize];
	free(dp);
	return res;
}

static int calcCombinationCount(const char* express, bool desired)
{
	if (!isExpressVaild(express)) return 0;

	int r1 = recur(express, desired, 0, strlen(express) - 1);
	int r2 = byStrictTable(express, desired);
	printf("%d,%d\n", r1, r2);
	return r2;
}

// 给定一个只由0(假)、1(真)、& (逻辑与)、 | (逻辑或)和 ^ (异或)五种字符组成的字符串express，再给定一个布尔值//desired.
// 返回express能有多少种组合方式，可以达到desired的结果。
// 示例:
//express = "1^0|0|1", desired = false
// 只有1 ^ ((0 | 0) | 1)和1 ^ (0 | (0 | 1))的组合可以得到false，返回2.
// express = "1", desired = false
// 无组合可以得到false，返回0.
//
//思路：
// 动态规划，先判断输入的字符是否合法，字符个数是奇数个，而且0, 2, 4, 6等偶数索引必定是数字，1, 3, 5, 7等奇数索引必定是逻辑运算符。
// 假设L < i < R, desired = true, i位置的字符是逻辑运算符& ，则看L~i - 1凑出true的方法有多少种(a)，i + 1~R凑出true的方法有多少种(b)，
	// 最终的方法数是a * b.
	// 沿着这个思路，依次处理字符串中的每一个逻辑运算符。
	//
	//characters:  1 ^ 0 | 0 | 1
	// indexes : 0  1  2  3  4  5  6
int main_DifferentLogicalOperatorOrderToMakeTrueOrFalse()
{
	char express[256] = "1^0|0|1";
	bool desired = false;
	int combinationCount = calcCombinationCount(express, desired);
	return 0;
}